package conclusion;

import java.util.Arrays;
import java.util.Random;

import data_structure.ListNode;

public class ArrayLinkedListOperation {

	public static ListNode<Integer> linkeListSum(ListNode<Integer> head1, ListNode<Integer> head2){
		if(head1 == null) return head2;
		if(head2 == null) return head1;
		
		int length1 = 0, length2 = 0;
		ListNode<Integer> ind1 = head1, ind2 = head2;
		
		while(ind1 != null){
			ind1 = ind1.next;
			length1++;
		}
		
		while(ind2 != null){
			ind2 = ind2.next;
			length2++;
		}
		
		ind1 = head1; ind2 = head2;
		int count = Math.abs(length1 - length2);
		ListNode<Integer> newhead = null, pre = null;
		ListNode<Integer> res = null;
		
		if(length1 != length2){
			if(length1 > length2){
				for(int i = 1 ; i <= count ; i++) ind1 = ind1.next;
				pre = head1;
				while(count > 1) pre = pre.next;
			}else{
				for(int i = 1 ; i <= count ; i++) ind2 = ind2.next;	
				pre = head2;
				while(count > 1) pre = pre.next;
			}
			
			res = sumUp(ind1, ind2);
			newhead = addCarry(head1, pre, res);
			if(newhead.val.doubleValue() > 10){
				ListNode<Integer> temp = newhead;
				newhead = new ListNode<Integer>(temp.val / 10);
				temp.val = temp.val % 10;
				newhead.next = temp;
			}
		}else{
			res = sumUp(ind1, ind2);
			if(res.val.doubleValue() > 10){
				newhead = new ListNode<Integer>(res.val / 10);
				newhead.next = res;
				res.val = res.val % 10;
			}else newhead = res;
		}
		return newhead;
	}
	
	private static ListNode<Integer> addCarry(ListNode<Integer> head1, ListNode<Integer> tail, ListNode<Integer> head2){
		ListNode<Integer> res = null;
		if(head1 == tail){
			res = new ListNode<Integer>(tail.val + head2.val / 10);
			head2.val = head2.val % 10;
			res.next = head2;
			return res;
		}else{
			res = new ListNode<Integer>(head1.val);
			res.next = addCarry(head1.next, tail, head2);
			if(res.next.val > 10){
				res.val = res.val + res.next.val / 10;
				res.next.val = res.next.val % 10;
			}
			return res;
		}
	}
	
	private static ListNode<Integer> sumUp(ListNode<Integer> node1, ListNode<Integer> node2){
		if(node1 == null || node2 == null) return null;
		ListNode<Integer> res = sumUp(node1.next, node2.next);
		ListNode<Integer> rres = null;
		int sum = node1.val + node2.val;
		
		if(res != null){
			sum += res.val / 10;
			res.val = res.val % 10;
		}
		
		rres = new ListNode<Integer>(sum);
		rres.next = res;
		return rres;
	}
	
	/**
	 * See LeetCode_day5
	 * Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
	 * If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
	 * You may not alter the values in the nodes, only nodes itself may be changed.
	 * Only constant memory is allowed.
	 * For example,
	 * Given this linked list: 1->2->3->4->5
	 * For k = 2, you should return: 2->1->4->3->5
	 * For k = 3, you should return: 3->2->1->4->5
	 * @param h
	 * @param k
	 */
	public static void reverseNodesInKGroup(ListNode h, int k){
		if(h == null || k < 2) return;
		
		ListNode dummy = new ListNode(null);
		dummy.next = h;
		ListNode pre= dummy;
		
		int count = 0;
		
		while(h != null){
			count++;
			if(count % k == 0){
				pre = reverse(pre, h.next);
				h = pre;
			}else h = h.next;
		}		
	}
	
	private static ListNode reverse(ListNode pre, ListNode next){
		ListNode last = pre.next;//the last node among (pre, next): the pre node of next
		ListNode cur = last.next;
		while(cur != next){
			last.next = cur.next;
			cur.next = pre.next;//the head of the currently reverted list
			pre.next = cur;
			cur = last.next;
		}
		return last;
	}
	
	public static void reverseNodeInKGroup1(ListNode h, int k){
		if(h == null || k < 2) return;
		int count = 0;
		ListNode dummy = new ListNode(null);
		dummy.next = h;
		ListNode pre= dummy;
		
		while(h != null){
			count++;
			if(count % k == 0){
				pre = reverse1(pre, h.next);
				h = pre;
			} h = h.next;
		}
		
		ListNode ind = dummy.next;
		while(ind != null){
			System.out.print(ind.val + ", ");
			ind = ind.next;
		}
	}
	
	private static ListNode reverse1(ListNode pre, ListNode next){
		ListNode last = pre.next;
		ListNode cur = last.next;
		ListNode p = last;
		while(cur != next){
			ListNode temp = cur.next;
			cur.next = p;
			p = cur;
			cur = temp;
		}
		pre.next = p;
		last.next = next;
		return last;
	}
	
	public static double medianOfTwoSortedArrayWithLengthN(int[] a1, int[] a2, int n){
		if(a1 == null || a2 == null || n <= 0) return -1;
		if(n == 1) return (a1[0] + a2[0]) /2.0;
		if(n == 2) return (Math.max(a1[0], a2[0]) + Math.min(a1[1], a2[1])) / 2.0;
		
		double m1 = -1, m2 = -1;
		if(n % 2 == 0){
			 m1 = (a1[n/2] + a1[n/2-1]) / 2.0;
			 m2 = (a2[n/2] + a2[n/2-1]) / 2.0;
		}else{
			m1 = a1[n/2];
			m2 = a2[n/2];
		}
		
		if(m1 == m2) return m1;
		else if(m1 < m2){
			if(n % 2 == 0){
				return medianOfTwoSortedArrayWithLengthN(Arrays.copyOfRange(a1, n/2, n), Arrays.copyOf(a2, n/2), n/2);
			}else{
				return medianOfTwoSortedArrayWithLengthN(Arrays.copyOfRange(a1, n/2, n), Arrays.copyOf(a2, n/2+1), n/2+1);
			}
		}else{
			if(n % 2 == 0){
				return medianOfTwoSortedArrayWithLengthN(Arrays.copyOf(a1, n/2), Arrays.copyOfRange(a2, n/2, n), n/2);
			}else{
				return medianOfTwoSortedArrayWithLengthN(Arrays.copyOf(a1, n/2+1), Arrays.copyOfRange(a2, n/2, n), n/2+1);
			}
		}
	}
	
	
	public static void bubbleSort(int[] a, int k){
		if(a == null || a.length < 2) return;
		
		for(int i = 0 ; i < k ; i++){
			for(int j = 0 ; j < a.length-1 ; j++){
				if(a[j] > a[j+1]){
					int t = a[j+1];
					a[j+1] = a[j];
					a[j] = t;
				}
			}
		}
	}
	
	public static void sortKSmallestlement(int[] a, int k, int start, int end){
		if(k > a.length || a == null) 
			return;
		if(start < end){
			int t = partition(a, start, end);//start <= t <= end
			sortKSmallestlement(a, k, start, t-1);
			if(t < k-1) sortKSmallestlement(a, k, t+1, end);
		}
	}
	
	
	public static int findkLargestElement(int[] a, int k, int start, int end){
		if(k > a.length || a == null) 
			return -1;
		if(start < end){
			int t = partition(a, start, end);//start <= t <= end
			if(t == k-1){ //kth in a[start : end]
				return a[t];
			}
			else if(t > k-1) return findkLargestElement(a, k, start, t-1);
			else return findkLargestElement(a, k, t+1, end);
		}if(start == end) return a[start];
		return -1;
	}
	
	public static int partition(int a[], int start, int end){
		Random r = new Random();
		int t = r.nextInt(end - start + 1) + start;
		int temp = a[end];
		a[end] = a[t];
		a[t] = temp;
		int ind = start;
		for(int i = start ; i < end ; i++){
			if(a[i] < a[end]){
				temp = a[ind];
				a[ind] = a[i];
				a[i] = temp;
				ind++;
			}
		}
		temp = a[ind];
		a[ind] = a[end];
		a[end] = temp;
		return ind;
	}
	
	public static int countInversion(int[] a, int start, int end){
		if(start >= end) return 0;
		else{
			int k = start + (end - start) / 2;
			int count = countInversion(a, start, k) + countInversion(a, k+1, end);
			//merge
			int[] t = new int[end-start+1];
			int ind1 = start, ind2 = k+1, ind3 = 0;
			while(ind1 <= k || ind2 <= end){
				if(ind1 > k){
					t[ind3++] = a[ind2++];
				}else if(ind2 > end){
					t[ind3++] = a[ind1++];
				}else{
					if(a[ind1] <= a[ind2]){
						t[ind3++] = a[ind1++];
					}else{
						t[ind3] = a[ind2];
						count += ind2-start-ind3;//key point
						//count = original position - current position
						ind3++; ind2++;
					}
				}
			}
			for(int i = start ; i <= end ; i++)
				a[i] = t[i-start];
			return count;
		}
	}
	
	
	public static void main(String[] args) {
		ListNode head1 = new ListNode(1);
		head1.next = new ListNode(2);
		head1.next.next = new ListNode(3);
		head1.next.next.next = new ListNode(4);
		head1.next.next.next.next = new ListNode(5);
		head1.next.next.next.next.next = new ListNode(6);
		
		reverseNodeInKGroup1(head1, 3);
		System.out.println();
		System.out.println("*****"+medianOfTwoSortedArrayWithLengthN(new int[]{1, 12, 15, 26}, new int[]{2, 13, 17, 30}, 4));
		
		int[] a =  new int[]{6,4,5,2,2,1};
		bubbleSort(a, 4);
		System.out.println();
		for(int i : a)
			System.out.print(i+", ");
		System.out.println();
		a = new int[]{6,4, 5, 7, 1, 2};
		System.out.println(findkLargestElement(a, 3, 0, 5));
		System.out.println();
		a = new int[]{6,5,4,7,1,2};
		sortKSmallestlement(a, 2, 0, 5);
		System.out.println();
		a = new int[]{6,5,4,7,1,2};
		System.out.println(countInversion(a, 0 , 5));
		System.out.println();
	}

}
